package com.xgh;

import java.math.BigDecimal;
import java.util.*;

/**
 * @ClassName EveryDay
 * @Description
 * @Author xinggh
 * @Date 2020/5/12 14:14
 * @Version 1.0
 **/
public class EveryDay {
    /**
     * 102. 二叉树的层序遍历
     *给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
     *
     *  
     *
     * 示例：
     * 二叉树：[3,9,20,null,null,15,7],
     *
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     * 返回其层次遍历结果：
     *
     * [
     *   [3],
     *   [9,20],
     *   [15,7]
     * ]
     * @param root
     * @return
     */
    /**
     * 广度遍历
     *
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {

        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Deque<TreeNode> deque = new LinkedList();
        deque.add(root);
        while (!deque.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int c = deque.size();
            for (int i = 0; i < c; i++) {
                TreeNode pop = deque.pop();
                list.add(pop.val);
                if (pop.left != null) {
                    deque.add(pop.left);
                }
                if (pop.right != null) {
                    deque.add(pop.right);
                }
            }

            result.add(list);
        }

        return result;
    }

    /**
     * 只出现一次的数字
     * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
     * <p>
     * 说明：
     * <p>
     * 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
     * <p>
     * 示例 1:
     * <p>
     * 输入: [2,2,1]
     * 输出: 1
     * 示例 2:
     * <p>
     * 输入: [4,1,2,1,2]
     * 输出: 4
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/single-number
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param nums
     * @return
     */
    public int singleNumber(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int tem = nums[0];
        for (int i = 1; i < nums.length; i++) {

            tem = tem ^ nums[i];
        }
        return tem;
    }

    /**
     * 560. 和为K的子数组
     * 给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
     * <p>
     * 示例 1 :
     * <p>
     * 输入:nums = [1,1,1], k = 2
     * 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
     * 说明 :
     * <p>
     * 数组的长度为 [1, 20,000]。
     * 数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。
     *
     * @param nums
     * @param k
     * @return
     */
    public static int subarraySum1(int[] nums, int k) {
        int len = nums.length;
        int result = 0;
        for (int i = 0; i < len; i++) {
            int sum = nums[i];
            if (sum == k) {
                result++;
            }
            for (int j = i + 1; j < len; j++) {
                sum = sum + nums[j];
                if (sum == k) {
                    result++;
                }
            }

        }
        return result;

    }

    //第二种解法；map
    public int subarraySum2(int[] nums, int k) {
        int count = 0, pre = 0;
        HashMap<Integer, Integer> mp = new HashMap<>();
        mp.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];
            if (mp.containsKey(pre - k))
                count += mp.get(pre - k);
            mp.put(pre, mp.getOrDefault(pre, 0) + 1);
        }
        return count;
    }

    /**
     * 25. K 个一组翻转链表
     * 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
     * <p>
     * k 是一个正整数，它的值小于或等于链表的长度。
     * <p>
     * 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
     * 示例：
     * <p>
     * 给你这个链表：1->2->3->4->5
     * <p>
     * 当 k = 2 时，应当返回: 2->1->4->3->5
     * <p>
     * 当 k = 3 时，应当返回: 3->2->1->4->5
     * <p>
     *  
     * <p>
     * 说明：
     * <p>
     * 你的算法只能使用常数的额外空间。
     * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
     *
     * @param head
     * @param k
     * @return
     */
  /*  public ListNode reverseKGroup(ListNode head, int k) {
        if (head.next == null || k == 1) {
            return head;
        }
        ListNode pre = head;
        ListNode start = head;
        ListNode end = null;
        int num = k - 1;
        while (pre.next != null) {
            end = pre.next;
            k--;
            if (num == 0) {
                reserve(start,end);
                num = k - 1;

            }
        }
    }

    public ListNode reserve(ListNode start,ListNode end)   {

        ListNode next = start.next;
        start.next = null;
        while (next == end) {
            ListNode next2 = next.next;
            next.next = start;
            start = next;
            next = next2;
        }
        return start;
    }*/
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode pre = dummy;
        ListNode end = dummy;

        while (end.next != null) {
            for (int i = 0; i < k && end != null; i++) {
                end = end.next;
                if (end == null) {
                    break;
                }
                ListNode start = pre.next;
                ListNode next = end.next;
                end.next = null;
                pre.next = reverse(start);
                start.next = next;
                pre = start;

                end = pre;
            }


        }
        return dummy.next;
    }

    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }


    /**
     * 152. 乘积最大子数组
     * 给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
     * 示例 1:
     * <p>
     * 输入: [2,3,-2,4]
     * 输出: 6
     * 解释: 子数组 [2,3] 有最大乘积 6
     * <p>
     * 示例 2:
     * <p>
     * 输入: [-2,0,-1]
     * 输出: 0
     * 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
     *
     * @param nums
     * @return
     */
    public static int maxProduct1(int[] nums) {
        //方法1.两次遍历所有子数组，并计算乘积，取最大
        int len = nums.length;
        int result = nums[0];
        for (int i = 0; i < len; i++) {
            result = Math.max(result, nums[i]);
            int sub = 1;
            for (int j = i + 1; j < len; j++) {
                sub = sub * nums[j];
                result = Math.max(result, sub * nums[i]);
            }

        }
        return result;
    }

    public static int maxProduct2(int[] nums) {
        //方法2.动态规划

        int max = Integer.MIN_VALUE, imax = 1, imin = 1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0) {
                int tmp = imax;
                imax = imin;
                imin = tmp;
            }
            imax = Math.max(imax * nums[i], nums[i]);
            imin = Math.min(imin * nums[i], nums[i]);

            max = Math.max(max, imax);
        }
        return max;


    }

    /**
     * 680. 验证回文字符串 Ⅱ
     * 给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
     * <p>
     * 示例 1:
     * <p>
     * 输入: "aba"
     * 输出: True
     * 示例 2:
     * <p>
     * 输入: "abca"
     * 输出: True
     * 解释: 你可以删除c字符。
     *
     * @param s
     * @return
     */
    public static boolean validPalindrome(String s) {

        return leftValid(s) || rightValid(s);
    }

    public static boolean leftValid(String s) {
        int len = s.length();
        boolean isDel = false;
        int i = 0, j = len - 1;
        while (i <= j) {
            if (s.charAt(i) == s.charAt(j)) {
                i++;
                j--;
            } else {
                if (isDel) {
                    return false;
                }
                i++;
                isDel = true;
            }
        }
        return true;
    }

    public static boolean rightValid(String s) {
        int len = s.length();
        boolean isDel = false;
        int i = 0, j = len - 1;
        while (i <= j) {
            if (s.charAt(i) == s.charAt(j)) {
                i++;
                j--;
            } else {
                if (isDel) {
                    return false;
                }
                j--;
                isDel = true;
            }
        }
        return true;
    }

    /**
     * 5. 最长回文子串
     * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
     * <p>
     * 示例 1：
     * <p>
     * 输入: "babad"
     * 输出: "bab"
     * 注意: "aba" 也是一个有效答案。
     * 示例 2：
     * <p>
     * 输入: "cbbd"
     * 输出: "bb"
     *
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len <= 1) {
            return s;
        }

        return "";
    }


    /**
     * s = "3[a]2[bc]", 返回 "aaabcbc".
     * s = "3[a2[c]]", 返回 "accaccacc".
     * s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/decode-string
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param s
     * @return
     */

    public static String decodeString(String s) {

        StringBuilder res = new StringBuilder();
        int multi = 0;
        LinkedList<Integer> stack_multi = new LinkedList<>();
        LinkedList<String> stack_res = new LinkedList<>();
        for (Character c : s.toCharArray()) {
            if (c == '[') {
                stack_multi.addLast(multi);
                stack_res.addLast(res.toString());
                multi = 0;
                res = new StringBuilder();
            } else if (c == ']') {
                StringBuilder tmp = new StringBuilder();
                int cur_multi = stack_multi.removeLast();
                for (int i = 0; i < cur_multi; i++) {
                    tmp.append(res);
                    res = new StringBuilder(stack_res.removeLast() + tmp);
                }
            } else if (c >= '0' && c <= '9') {
                multi = multi * 10 + Integer.parseInt(c + "");
            } else {
                res.append(c);
            }
        }
        return res.toString();
    }


    /**
     * 287. 寻找重复数
     * 给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
     *
     * 示例 1:
     *
     * 输入: [1,3,4,2,2]
     * 输出: 2
     * 示例 2:
     *
     * 输入: [3,1,3,4,2]
     * 输出: 3
     *
     * 说明：
     *
     * 不能更改原数组（假设数组是只读的）。
     * 只能使用额外的 O(1) 的空间。
     * 时间复杂度小于 O(n2) 。
     * 数组中只有一个重复的数字，但它可能不止重复出现一次
     * @param nums
     * @return public int findDuplicate(int[] nums) {

    }*/

    /**
     * [1,2,3,1]
     * 输出: 4
     * 解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     *      偷窃到的最高金额 = 1 + 3 = 4 。
     * 示例 2:
     * <p>
     * 输入: [2,7,9,3,1]
     * 输出: 12
     * 解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     *      偷窃到的最高金额 = 2 + 9 + 1 = 12 。
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/house-robber
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        //动态规划
        int len = nums.length;
        int dp[] = new int[len + 1];
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 2; i < len; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        return dp[len];
    }


    /**
     * 1431. 拥有最多糖果的孩子
     * 给你一个数组 candies 和一个整数 extraCandies ，其中 candies[i] 代表第 i 个孩子拥有的糖果数目。
     * <p>
     * 对每一个孩子，检查是否存在一种方案，将额外的 extraCandies 个糖果分配给孩子们之后，此孩子有 最多 的糖果。
     * 注意，允许有多个孩子同时拥有 最多 的糖果数目。
     * <p>
     * 示例 2：
     * <p>
     * 输入：candies = [4,2,1,1,2], extraCandies = 1
     * 输出：[true,false,false,false,false]
     * 解释：只有 1 个额外糖果，所以不管额外糖果给谁，只有孩子 1 可以成为拥有糖果最多的孩子。
     * 示例 3：
     * <p>
     * 输入：candies = [12,1,12], extraCandies = 10
     * 输出：[true,false,true]
     *
     * @param candies
     * @param extraCandies
     * @return
     */
    public static List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
        List<Boolean> result = new ArrayList<>();
        int len = candies.length;
        int max = candies[0];
        for (int i = 1; i < len; i++) {
            if (candies[i] >= max) {
                max = candies[i];
            }
        }

        int diff = max - extraCandies;
        for (int j = 0; j < len; j++) {
            if (candies[j] >= diff) {
                result.add(true);
            } else {
                result.add(false);
            }
        }
        return result;
    }

    /**
     * 面试题64. 求1+2+…+n
     * 求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
     *
     * @param n
     * @return
     */
    public static int sumNums(int n) {


        int sum = n / 2 * (n + 1) + n % 2 * (n / 2 + 1);

        return sum;

    }

    /**
     * 837. 新21点
     * 爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏，描述如下：
     *
     * 爱丽丝以 0 分开始，并在她的得分少于 K 分时抽取数字。 抽取时，她从 [1, W] 的范围中随机获得一个整数作为分数进行累计，
     * 其中 W 是整数。 每次抽取都是独立的，其结果具有相同的概率。
     *
     * 当爱丽丝获得不少于 K 分时，她就停止抽取数字。 爱丽丝的分数不超过 N 的概率是多少？
     *
     * 示例 1：
     *
     * 输入：N = 10, K = 1, W = 10
     * 输出：1.00000
     * 说明：爱丽丝得到一张卡，然后停止。
     * 示例 2：
     *
     * 输入：N = 6, K = 1, W = 10
     * 输出：0.60000
     * 说明：爱丽丝得到一张卡，然后停止。
     * 在 W = 10 的 6 种可能下，她的得分不超过 N = 6 分。
     * 示例 3：
     *
     * 输入：N = 21, K = 17, W = 10
     * 输出：0.73278
     * @param N
     * @param K
     * @param W
     * @return
     */
    /*public double new21Game(int N, int K, int W) {

    }*/

    /**
     * 238. 除自身以外数组的乘积
     * 给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
     * <p>
     * <p>
     * <p>
     * 示例:
     * <p>
     * 输入: [1,2,3,4]
     * 输出: [24,12,8,6]
     *
     * @param nums
     * @return
     */
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;

        int left[] = new int[len];
        int right[] = new int[len];
        int result[] = new int[len];


        left[0] = 1;
        for (int i = 1; i < len; i++) {
            left[i] = nums[i - 1] * left[i - 1];
        }

        right[len - 1] = 1;
        for (int i = len - 2; i < 0; i--) {
            right[i] = right[i + 1] * nums[i + 1];
        }

        for (int i = 0; i < len; i++) {
            result[i] = left[i] * right[i];
        }
        return result;
        /**
         *   int[] res = new int[nums.length];
         *         int k = 1;
         *         for(int i = 0; i < res.length; i++){
         *             res[i] = k;
         *             k = k * nums[i]; // 此时数组存储的是除去当前元素左边的元素乘积
         *         }
         *         k = 1;
         *         for(int i = res.length - 1; i >= 0; i--){
         *             res[i] *= k; // k为该数右边的乘积。
         *             k *= nums[i]; // 此时数组等于左边的 * 该数右边的。
         *         }
         *         return res;
         *
         * 作者：LDouble
         * 链接：https://leetcode-cn.com/problems/product-of-array-except-self/solution/cheng-ji-dang-qian-shu-zuo-bian-de-cheng-ji-dang-q/
         * 来源：力扣（LeetCode）
         * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
         */
    }

    /**
     * 面试题29. 顺时针打印矩阵
     * 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
     * <p>
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
     * 输出：[1,2,3,6,9,8,7,4,5]
     * 示例 2：
     * <p>
     * 输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
     * 输出：[1,2,3,4,8,12,11,10,9,5,6,7]
     *
     * @param matrix
     * @return
     */
    public int[] spiralOrder(int[][] matrix) {

        int m = matrix.length;
        if (m == 0) {
            return new int[]{};
        }
        int n = matrix[0].length;
        int top = 0, bot = m - 1, left = 0, right = n - 1;      //设置上下左右界限
        int cnt = 0;
        int[] res = new int[m * n];
        while (top <= bot && left <= right) {
            for (int j = left; j <= right; j++) {                   //从左到右
                res[cnt++] = matrix[top][j];
            }
            top++;
            for (int i = top; i <= bot; i++) {                      //从上到下
                res[cnt++] = matrix[i][right];
            }
            right--;
            for (int j = right; j >= left && top <= bot; j--) {         //从右到左
                res[cnt++] = matrix[bot][j];
            }
            bot--;
            for (int i = bot; i >= top && left <= right; i--) {         //从下到上
                res[cnt++] = matrix[i][left];
            }
            left++;

        }

        return res;
    }

    /**
     * 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
     * <p>
     * 说明：本题中，我们将空字符串定义为有效的回文串。
     * <p>
     * 示例 1:
     * <p>
     * 输入: "A man, a plan, a canal: Panama"
     * 输出: true
     * 示例 2:
     * <p>
     * 输入: "race a car"
     * 输出: false
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/valid-palindrome
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param s
     * @return
     */
    public static boolean isPalindrome(String s) {
        if (s.equals("") || s.trim().equals("") || s.length() == 1) {
            return true;
        }
        int i = 0;
        int j = s.length() - 1;
        while (i <= j) {
            while (i <= j && !checkChar(s.charAt(i))) {
                i++;
            }

            while (i <= j && !checkChar(s.charAt(j))) {
                j--;
            }
            if (i > j) {
                return false;
            }
            if (s.charAt(i) == s.charAt(j) || s.charAt(i) == (s.charAt(j) + 32) || s.charAt(i) == (s.charAt(j) - 32)) {
                i++;
                j--;
            } else {
                return false;
            }

        }
        return true;
    }

    public static boolean checkChar(char c) {
        if ((c >= 65 && c <= 90) || (c >= 97 && c <= 122) || c >= 48 && c <= 57) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {

        isPalindrome(".,");

        int nums[] = {0, -2, -2, -3, 0};
      /*  BigDecimal b1 = new BigDecimal(Integer.valueOf(1501));
        BigDecimal b2 = new BigDecimal(Integer.valueOf(5));
        BigDecimal multiply = b1.multiply(b2);
        String s = multiply.divide(new BigDecimal("100")).toString();
        System.out.println(s);*/
       /* int[] nums = {1, 1, 1};

        System.out.println(subarraySum1(nums, 1));*/
        //System.out.println(maxProduct2(nums));
      /*  Student l = new Student();
        System.out.println(l == null);
        System.out.println(l.getName());

        System.out.println(validPalindrome("abefba"));*/
        //decodeString("3[a2[c]]");
      /*  int candies[] = {2, 3, 5, 1, 3};
        int extraCandies = 3;
        System.out.println(kidsWithCandies(candies, extraCandies));*/

        //System.out.println(sumNums(9));
        int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        List list = new ArrayList();

        for (int i = 0; i < matrix.length; i++) {

        }


    }


}
